package com.lw.leetcode.back.b;

/**
 * 494. 目标和
 * 剑指 Offer II 102. 加减的目标值
 *
 * @Author liw
 * @Date 2021/6/7 13:16
 * @Version 1.0
 */
public class FindTargetSumWays {

    public static void main(String[] args) {
        FindTargetSumWays test = new FindTargetSumWays();
        int[] arr = {1};
        int targetSumWays = test.findTargetSumWays(arr, 1);
        System.out.println(targetSumWays);
    }

    long sum = 0;
    int count = 0;
    int target;

    public int findTargetSumWays(int[] nums, int target) {
        this.target = target;
        find(nums, 0);
        return count;
    }

    private void find(int[] nums, int index) {
        if (nums.length == index) {
            if (sum == target) {
                count++;
            }
            return;
        }
        int value = nums[index];
        sum += value;
        find(nums, index + 1);
        sum -= (value << 1);
        find(nums, index + 1);
        sum += value;
    }
}
